//2171.拿出最少数目的魔法豆
//https://leetcode.cn/problems/removing-minimum-number-of-magic-beans/?envType=daily-question&envId=Invalid%20Date
class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        //排序+前缀和
        long long ret = LONG_MAX;
        //排序计算前缀和
        long long n = beans.size();
        sort(beans.begin(),beans.end());
        vector<long long> sum(n+1,0);
        for(int i = 0;i<n;++i) sum[i+1] = sum[i]+beans[i];

        //枚举切割点 分为左边和右边
        //左边的点全部变为0 变化数为 sum[i]
        //右边全部变为beans[i] 变化数为 sum[n] - (n-i)*beans[i]
        //将左右变化减去得出 sum[n] - (n-i)*beans[i] - sum[i];
        //求出分割左右时变化的最小值即可
        for(long long i = 0;i<n;++i)
        {
            long long left = sum[i];
            long long right = sum[n]-sum[i]-((n-i)*beans[i]);
            ret = min(ret,left+right);
        }
        return ret;
    }
};